Melancholy

Time Limit: 10 Sec Memory Limit: 256 MB

Description

DX3906星系，Melancholy星上，我在勘测这里的地质情况。
　　我把这些天来已探测到的区域分为N组，并用二元组(D,V)对每一组进行标记：其中D为区域的相对距离，V为内部地质元素的相对丰富程度
　　在我的日程安排表上有Q项指派的计划。
　　每项计划的形式是类似的，都是“对相对距离D在[L,R]之间的区域进行进一步的勘测，并在其中有次序地挑出K块区域的样本进行研究。”采集这K块的样品 后，接下来在实验中，它们的研究价值即为这K块区域地质相对丰富程度V的乘积。
　　我对这Q项计划都进行了评估：一项计划的评估值P为所有可能选取情况的研究价值之和。
　　但是由于仪器的原因，在一次勘测中，这其中V最小的区域永远不会被选取。
　　现在我只想知道这Q项计划的评估值对2^32取模后的值，特殊地，如果没有K块区域可供选择， 评估值为0。

Input

第一行给出两个整数，区域数N与计划数Q。
　　第二行给出N个整数，代表每一块区域的相对距离D。
　　第三行给出N个整数，代表每一块区域的内部地质元素的相对丰富程度V。
　　接下来的Q行，每一行3个整数，代表相对距离的限制L,R，以及选取的块数K。

Output

输出包括Q行，每一行一个整数，代表这项计划的评估值对2^32取模后的值。

Sample Input

5 3
　　5 4 7 2 6
　　1 4 5 3 2
　　6 7 1
　　2 6 2
　　1 8 3

Sample Output

5
　　52
　　924

img

HINT

img

Main idea

查询D在[L, R]中的元素，去掉最小的L值之后，任意k几个相乘的和。

Solution

首先，我们可以按照D排序一下，然后调出D在[L,R]的元素，显然是连续的一段。

然后我们再记录一下最小值L，以及最小值L所在的位置。这样在线段树上区间查询一下，就可以得到最小值的pos。

那么我们就将询问化成了，查询两个区间的信息并且合并。

问题在于如何合并。

我们对于线段树上的每个节点，记录一下val[i]表示选了i个乘起来的和。

那么两个区间合并起来时，val[i] = ΣA.val[j] * B.val[i - j]，根据乘法分配律可以看出。

比如我们左区间选了2个的答案形如：x1·x2 + y1·y2，右区间选了1个的答案形如：z1 + z2。

那么合并之后的区间 选了3个答案形如：x1·x2·z1 + x1·x2·z2 + y1·y2·z2+ y1·y2·z2，显然就是两个乘起来，并且不漏状态。

这样就可以得到答案啦。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int u32;

const int ONE = 1000005;
const int MOD = 1e9 + 7;
const u32 INF = 4294967295u;

int n, Q;
int k;
struct point
{
    u32 d, v;
}a[ONE], L, R;
bool cmp(const point &a, const point &b) {return a.d < b.d;}

struct power
{
    u32 val[7];
    friend power operator +(power a, power b)
    {
        power c;
        for(int i = 1; i <= 6; i++) c.val[i] = a.val[i] + b.val[i];
        for(int i = 1; i <= 6; i++)
            for(int j = 1; j < i; j++)
                c.val[i] += a.val[j] * b.val[i - j];
        return c;
    }
}Node[ONE], A[3], Ans;

struct Min
{
    u32 val, pos;
    friend Min operator +(Min a, Min b)
    {
        Min c = (Min){INF, 0};
        if(a.val < c.val) c = a;
        if(b.val < c.val) c = b;
        return c;
    }
}Val[ONE], res_min;

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

namespace Seg
{
    void Build(int i, int l, int r)
    {
        Val[i] = (Min){INF, 0};
        for(int j = 1; j <= 6; j++) Node[i].val[j] = 0;
        if(l == r)
        {
            Node[i].val[1] = a[l].v;
            Val[i] = (Min){a[l].v, l};
            return;
        }
        int mid = l + r >> 1;
        Build(i << 1, l, mid); Build(i << 1 | 1, mid + 1, r);
        Node[i] = Node[i << 1] + Node[i << 1 | 1];
        Val[i] = Val[i << 1] + Val[i << 1 | 1];
    }

    void Find(int i, int l, int r, int L, int R)
    {
        if(L > R) return;
        if(L <= l && r <= R)
        {
            res_min = res_min + Val[i];
            return;
        }
        int mid = l + r >> 1;
        if(L <= mid) Find(i << 1, l, mid, L, R);
        if(mid + 1 <= R) Find(i << 1 | 1, mid + 1, r, L, R);
    }

    void Query(int i, int l, int r, int L, int R, int opt)
    {
        if(L > R) return;
        if(L <= l && r <= R)
        {
            A[opt] = A[opt] + Node[i];
            return;
        }
        int mid = l + r >> 1;
        if(L <= mid) Query(i << 1, l, mid, L, R, opt);
        if(mid + 1 <= R) Query(i << 1 | 1, mid + 1, r, L, R, opt);
    }
}

void Deal(int k)
{
    int Left = lower_bound(a + 1, a + n + 1, L, cmp) - a;
    int Right = upper_bound(a + 1, a + n + 1, R, cmp) - a - 1;
    if(Left >= Right) {printf("0\n"); return;}

    res_min = (Min){INF, 0};
    Seg::Find(1, 1, n, Left, Right);

    for(int i = 1; i <= 6; i++) A[1].val[i] = A[2].val[i] = 0;
    Seg::Query(1, 1, n, Left, res_min.pos - 1, 1);
    Seg::Query(1, 1, n, res_min.pos + 1, Right, 2);

    Ans = A[1] + A[2];
    for(u32 i = 1; i <= k; i++) Ans.val[k] *= i;
    printf("%u\n", Ans.val[k]);
}

int main()
{
    n = get();    Q = get();
    for(int i = 1; i <= n; i++) a[i].d = get();
    for(int i = 1; i <= n; i++) a[i].v = get();
    sort(a + 1, a + n + 1, cmp);

    Seg::Build(1, 1, n);

    while(Q--)
    {
        L.d = get(), R.d = get(), k = get();
        Deal(k);
    }
}